<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
<title>算法</title>
<meta name="description" content="">
<meta name="keywords" content="">
<link href="" rel="stylesheet">
<script>
	// 冒泡
	// 1
	function bubbleSort(arr){
		var len = arr.length;
		for(var i = 0;  i<len; i++){
			for(var j; j<len-1-i; j++){
				if(arr[j]>arr[i+1]){
					var temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
				}
			}
		}
		return arr;
	}
	// 2 标记变量 改进
	function bubbleSort2(arr){
		var i = arr.length-1;
		while(i>0){
			var pos = 0;
			for(var j = 0; j<i; j++){
				if(arr[j]<arr[j+1]){
					pos = j;
					var temp = arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=temp;
				}
				i=pos;
			}
			return arr;
		}
	}

	// 3 正反向排序 改进
	 function bubbleSort3(arr){
	 	var low = 0;
	 	var high = arr.length-1;
	 	var temp,j;
	 	while(low<high){
	 		// 正向
	 		for(j=low;j<high;++j){
	 			if(arr[j]>arr[j+1]){
		 			temp = arr[j];
		 			arr[j]=arr[j+1];
		 			arr[j+1]=temp;
	 			}
	 		}
	 		--high;
	 		// 反向
	 		for(j=high;j>low;--j){
	 			if(arr[j]<arr[j-1]){
	 				temp=arr[j];
	 				arr[j]=arr[j-1];
	 				arr[j-1]=temp;
	 			}
	 		}
	 		++low;
	 	}
	 	return arr;
	 }

	 // 选择排序 找到最小的index
	 function selectionSort(arr){
	 	var len = arr.length;
	 	var minIndex,temp;
	 	for(var i=0;i<len-1;i++){
	 		minIndex =i;
	 		for(var j=i+1;j<len;j++){
	 			if(arr[j]<arr[minIndex]){
	 				minIndex = j;
	 			}
	 		}
	 		temp = arr[i];
	 		arr[i]=arr[minIndex];
	 		arr[minIndex] =temp;
	 	}
	 	return arr;
	 }



	 //  插入算法
	 // 1
	 function insertSort(arr){
	 	if (Object.prototype.toString.call(arr).slice(8,-1)==='Array') {
	 		for(var i=1;i<arr.length; i++){
	 			var key = arr[i];
	 			var j = i-1;
	 			while(j>0&& arr[j]>key){
	 				arr[j+1]=arr[j];
	 				j--;
	 			}
	 			arr[j+1]=key;
	 		}
	 		return arr;
	 	}else{
	 		return 'arr is not an Array';
	 	}
	 }




	 // 2 改进 二分查找
	function insertionSort(array) {
	    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
	        console.time('插入排序耗时：');
	        for (var i = 1; i < array.length; i++) {
	            var key = array[i];
	            var j = i - 1;
	            while (j >= 0 && array[j] > key) {
	                array[j + 1] = array[j];
	                j--;
	            }
	            array[j + 1] = key;
	        }
	        console.timeEnd('插入排序耗时：');
	        return array;
	    } else {
	        return 'array is not an Array!';
	    }
	}





	// shell 希尔
	function shellSort(arr) {
	    var len = arr.length,
	        temp,
	        gap = 1;
	    console.time('希尔排序耗时:');
	    while(gap < len/5) {          //动态定义间隔序列
	        gap =gap*5+1;
	    }
	    for (gap; gap > 0; gap = Math.floor(gap/5)) {
	        for (var i = gap; i < len; i++) {
	            temp = arr[i];
	            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
	                arr[j+gap] = arr[j];
	            }
	            arr[j+gap] = temp;
	        }
	    }
	    console.timeEnd('希尔排序耗时:');
	    return arr;
	}

	 // 归并排序
	 function mergeSort(arr) {  //采用自上而下的递归方法
	    var len = arr.length;
	    if(len < 2) {
	        return arr;
	    }
	    var middle = Math.floor(len / 2),
	        left = arr.slice(0, middle),
	        right = arr.slice(middle);
	    return merge(mergeSort(left), mergeSort(right));
	}	
	function merge(left, right)
	{
	    var result = [];
	    console.time('归并排序耗时');
	    while (left.length && right.length) {
	        if (left[0] <= right[0]) {
	            result.push(left.shift());
	        } else {
	            result.push(right.shift());
	        }
	    }
	    while (left.length)
	        result.push(left.shift());
	    while (right.length)
	        result.push(right.shift());
	    console.timeEnd('归并排序耗时');
	    return result;
	}
	var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
	console.log(mergeSort(arr));



	
</script>
</head>
<body>
    














</body>
</html>